Vehicles may be equipped with many sensors that allow the vehicles to perceive other vehicles, obstacles, pedestrians, and other features of a surrounding environment. Moreover, the vehicles can use information about perceived features in the surrounding environment to localize the vehicle within the environment. That is, the vehicle can correlate perceived features (e.g., road markings, terrain, etc.) with mapped features to determine a position of the vehicle within the environment. This process is generally referred to as simultaneous localization and mapping (SLAM) and produces a map with position information for the mapped features that is a basis for comparison to perform the localization.
However, as aspects of an environment change from construction or other causes, the changes can cause difficulties with features of the map not aligning as expected thereby resulting in reduced accuracy and other difficulties with localizing the vehicle according to the map. Moreover, dynamic changes within the environment such as traffic at different times of the day (e.g., rush hour), weather (e.g., snow), seasonal changes (e.g., leaves on trees), temporary structures (e.g., tents) and other transient aspects can complicate detecting changes to more integral or static aspects of the environment such as roadways, terrain, buildings, etc. and may interfere with maintaining an accurate portrayal of the environment using the map. Consequently, accurately identifying changes within an environment presents many difficulties.